from graph import Graph,bsf


def buildMap(filename):
    G = Graph()
    with open(filename,"r",encoding="utf8") as f:
        maze = f.readlines()
    H = len(maze)
    W = len(maze[1])
    exits = list()
    for i,line in enumerate(maze):
        line = line.strip("\n")
        for j,pos in enumerate(line):
            if pos == "+":
                continue
            if pos == "S":
                start = (i,j)
            if j == 0 or i == 0 or j == W-1 or i == H-1:
                exits.append((i,j))
            for x,y in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
                if x < 0 or y < 0 or x >= H or y>=W:
                    continue
                if maze[x][y] == "+":
                    continue
                G.addEdge((i,j),(x,y))
    return G,start,exits,H*W

def traverse(y):
    x = y
    while x.getPred():
        print(x.getId())
        x = x.getPred()
    print(x.getId())

def show_path(filename,path,start):
    with open(filename,"r",encoding="utf8") as f:
        maze = f.readlines()
    for i,line in enumerate(maze):
        line = line.strip("\n")
        maze[i] = [pos for pos in line]
    for pos in path[:-1]:
        maze[pos[0]][pos[1]] = "#"
    for line in maze:
        print("".join(line))


if __name__ == "__main__":
    G,start,exits,size = buildMap("maze2.txt")
    bsf(G.getVertex(start))
    minPath = [None]*size
    for exitPos in exits:
        nowPos = G.getVertex(exitPos)
        path = list()
        while nowPos.getPred():
            path.append(nowPos.getId())
            nowPos = nowPos.getPred()
        path.append(nowPos.getId())
        if len(path) <= len(minPath):
            minPath = path
    show_path("maze2.txt",path,start)

        